A control device of a vehicle is well known as a control device of a vehicle including a multi-speed transmission having a plurality of gear positions different in gear ratio selectively established by controlling engagement and release of predetermined engagement devices out of a plurality of engagement devices. For example, this corresponds to a vehicle control device described in Patent Document 1. In Patent Document 1, it is disclosed that, when gears are shifted in an automatic transmission where the gear shifting is achieved by switching engagement and release of engagement devices, a transmission torque of a release-side engagement device (the engagement device to be released) starts decreasing before completing the packing of an engagement-side engagement device (the engagement device to be engaged), resulting in an insufficient total transmission torque of the engagement-side engagement device and the release-side engagement device possibly causing a shift shock and that, in this regard, by estimating a time required for the packing of the engagement-side engagement device based on oil temperature of the automatic transmission and by providing a temporal difference in timing of output between an increase start command for the transmission torque related to the engagement-side engagement device and a decrease start command for the transmission torque related to the release-side engagement device based on the time required for the packing, the shift shock due to the insufficient total transmission torque is suppressed.